Reorder List

LeetCode 143 | Difficulty: Medium

Medium

Problem Description

You are given the head of a singly linked-list. The list can be represented as:

L~0~ → L~1~ → … → L~n - 1~ → L~n~

Reorder the list to be on the following form:

L~0~ → L~n~ → L~1~ → L~n - 1~ → L~2~ → L~n - 2~ → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

- The number of nodes in the list is in the range `[1, 5 * 10^4]`.

- `1 <= Node.val <= 1000`

Topics: Linked List, Two Pointers, Stack, Recursion

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 186 ms)

Metric	Value
Runtime	186 ms
Memory	N/A
Date	2017-10-06

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void ReorderList(ListNode head) {
        if(head==null || head.next == null || head.next.next == null) return;

        ListNode s = head, f = head;
        while (f != null && f.next != null)
        {
            s = s.next;
            f = f.next.next;
        }
        ListNode h1 = head, h2 = s.next;
        s.next = null;
        h2 = Reverse(h2);
        ListNode final = new ListNode(Int32.MinValue);
        ListNode tail = final;
        while (h1 != null && h2!=null)
        {
            tail.next = h1;
            tail = h1;
            h1 = h1.next;
            tail.next = h2;
            tail = h2;
            h2 = h2.next;   
            tail.next = null;
        }
        if(h1!=null)
        tail.next = h1;
        if(h2!=null)
        tail.next = h2;
        head = final.next;
    }
    private static ListNode Reverse(ListNode head)
    {
        ListNode rev = null;
        while (head != null)
        {
            ListNode temp = head;
            head = head.next;
            temp.next = rev;
            rev = temp;
        }
        return rev;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Stack	$O(n)$	$O(n)$
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?